1. Field of the Invention
This invention relates generally to computer networking, and more particularly to micro-flow based label switched path utilization over a computer network.
2. Description of the Related Art
Due to high customer demand for increasingly reliable and differentiated services, today's Internet Service Providers (ISPs) are constantly faced with the challenge of adapting their networks to support increased customer demand and growth. As a result, many ISPs rely upon conventional switches and network servers to connect dial-in port concentrators to backbone networks, such as the Internet. In the past, these servers and port concentrators typically communicated with each other through the use of an Internet Protocol (IP), while the port concentrators typically communicated with the network backbone through asynchronous transfer mode (ATM) protocol.
The previously described configuration is often referred to as an IP over ATM model. IP over ATM uses an overlay model in which a logical IP routed topology runs over and is independent of an underlying Open Systems Interconnection (OSI) Layer 2 switched ATM topology. The OSI Reference Model is the International Organization for Standard's (ISO) layered communication protocol model.
The Layer 2 switches provide high-speed connectivity, while the IP routers at the edge, interconnected by a mesh of Layer 2 virtual circuits, provide the intelligence to forward IP datagrams.
Although, the ATM switches provided high bandwidth, the requirement of costly network interface cards, 10% “cell tax” overhead, numerous system interrupts, and poor routing stability reduce its effectiveness. Moreover, the growth of Internet services and Wavelength Division Multiplexing (WDM) technology at the fiber level has provided a viable alternative to ATM for multiplexing multiple services over individual circuits. Moreover, ATM switches currently are being out-performed by Internet backbone routers, and multilayer switching paradigms, such as Mulitprotocol Label Switching (MPLS) offer simpler mechanisms for packet-oriented traffic engineering (TE) and multiservice functionality. Hence, many ISPs currently utilize MPLS technology to provide label path switching as the method to interconnect multiple transit devices instead of ATM technology.
The basic function of MPLS is to provide a Layer 2 Label Switched Path (LSP), which is similar to ATM, to transport one or more traffic flows over a predetermined path. The path is generally traffic engineered (TE) to maximize the usage of the physical links within the network that were under-utilized using the existing routing algorithm. Once an LSP is established, the LSP becomes a logical link and is integrated into the Layer 3 routing topology. When a packet is transported over the LSP, a Layer 2 switching function is performed for fast packet forwarding.
A conventional MPLS protocol includes a signaling component and a forwarding component. The signaling component is used to establish LSPs based on either traffic engineered information or dynamic routing information. Once a LSP is established, the associated incoming and outgoing labels at each label switched router (LSR) form a forwarding entry in a MPLS forwarding table, which is used by the forwarding component to perform fast packet forwarding on the labeled MPLS packets.
When packets arrive, the forwarding component searches the forwarding table to make a routing decision for each packet. Specifically, the forwarding component examines the incoming MPLS label and searches for a match. If there is a match, the packet is directed to the appropriate outgoing interface across the system's switching fabric.
The header of each packet is generally given a label, which is a short, fixed length value that identifies a Forwarding Equivalence Class (FEC) for the packet. Each FEC is a set of packets that are forwarded over the same path through a network, even if the individual packets' ultimate destinations are different. Label switches use the FEC to determine which LSP to utilize for transmitting the packet. It should be noted that a plurality of FECs may be mapped to the same LSP, and likewise, more than one LSP may be mapped to each FEC. The packet is then transmitted using the selected LSP, which defines an ingress-to-egress path through the network that is followed by all packets assigned to a specific FEC.
In the core of the network, label switches ignore the packet's network layer header and simply forward the packet using the packet's label. Basically, when a labeled packet arrives at a label switch, the forwarding component uses the input port number and label to perform an exact match search of its forwarding table. When a match is found, the forwarding component retrieves the next hop address from the forwarding table and directs the packet to the outbound interface for transmission to the next hop in the LSP.
This allows for the OSI interconnection Layer to by-pass having to look in the individual Layer 3 destinations and to simply route based upon the MPLS labels. Moreover, a MPLS topology allows for a network control application to monitor the LSPs that are established in the network and, allows the application to create new LSPs as the traffic between routers changes, either in direction or in size.
However, traffic from users is not always predictable, and hence excess capacity must be provided in each LSP to ensure available bandwidth during rerouting. High levels of flow aggregation require a higher amount of excessive bandwidth to be provisioned on each LSP to support transient “burstiness” of the traffic load, which is an extremely inefficient use of network resources. Moreover, routing with aggregated flows through the network causes significant strain and shift as the network re-aligns during failure, as shown next with reference to FIGS. 1A and 1B.
FIG. 1A is an illustration showing a conventional LSP based network 100. The conventional LSP based network 100 includes label switches 102, 104, and 106, a first LSP 108 connecting label switch 102 to label switch 106, and a second LSP 110a connecting label switch 102 to label switch 104. Finally, each LSP includes a large aggregate flow 112a and 112b, comprised of a plurality of individual data flows.
Each individual flow is a group of IP data packets from a single data transmission, wherein each IP data packet in the flow includes the same source address, destination address, source port, destination port, and IP protocol type. In addition, each packet of the flow follows the preceding packet by no more than a predetermined amount of time, for example, 2 milliseconds (ms).
During normal operation the conventional LSP based network 100 functions satisfactorily. Specifically, the individual flows included in the aggregate flows 112a and 112b of each LSP 108 and 110a reach their respective destinations in a satisfactory manner. However, when unexpected rerouting occurs, problems arise, as shown next with reference to FIG. 1B.
FIG. 1B is an illustration of a conventional LSP based network 100 having an unusable LSP. In the FIG. 1B, the second LSP 110a connecting label switch 102 to label switch 104 is no longer usable, for example, because of congestion or physical wire failure. In this case, the aggregate flow 112b included in the second LSP 110a must be rerouted along a third LSP 110b, which connects label switch 102 to label switch 104 via label switch 106. However, as shown in FIG. 1B, the third LSP 110b and the first LSP 108 share a common path, specifically, the connection between label switch 102 and label switch 106. Hence, the first LSP 108 must include enough bandwidth to accommodate the entire bandwidth of the second LSP 110a, which was rerouted to the third LSP 110b. 
FIG. 1B illustrates the difficulty of rerouting large aggregate flows. To ensure available bandwidth for rerouting, LSP 108 must always reserve enough bandwidth to accommodate adjacent LSPs in the event of a reroute, such as rerouted LSP 110b shown in FIG. 1B. Since such a large bandwidth reserve, or threshold, is needed to accommodate unexpected flow increases, link utilization is low. For example, if 50% of a link's bandwidth is utilized by its aggregate flow, the other 50% may have to be reserved in case of an unexpected flow reroute. Hence, 50% of the link bandwidth is not utilized during general operation.
Moreover, fault recovery in a conventional LSP based network is slow, typically 20 seconds to 2 minutes. This slow fault recovery time results from a lack of control over the individual flows within each LSP. As stated previously, a conventional LSP based network routes each individual flow to a particular LSP based on the FEC associated with each individual flow. However, once an individual flow is routed to a particular LSP, the network can no longer efficiently alter the path of the individual flow. As a result, if a particular switch or area of an LSP is disabled, local repair can occur, however such new path will not be the most efficient at transporting the micro-flows. In addition, when a fault at a particular switch occurs, the failure indication is not communicated to the source node in real time. Hence, end-to-end recovery is delayed, typically resulting in network congestion.
In view of the forgoing, there is a need for an intelligent traffic engineering protocol that provides load balancing based on the utilization of individual LSPs. In addition, the protocol should integrate OSI based Layer 2 and OSI based Layer 3 switching, provide good traceability of data flows, and allow for fast fault recovery.